#include "main/utils.h"
using namespace std;

int findFather(vector<int>& fathers, int i) {
  if (fathers[i] != i) {
    fathers[i] = findFather(fathers, fathers[i]);
  }
  return fathers[i];
}

bool merge(vector<int>& fathers, vector<int> edge) {
  int father_0 = findFather(fathers, edge[0]);
  int father_1 = findFather(fathers, edge[1]);
  if (father_0 != father_1) {
    fathers[father_0] = father_1;
    return true;
  }
  return false;
}

vector<int> findRedundantEdge(const vector<vector<int>>& edges) {
  int num = INT_MIN;
  for (auto edge : edges) {
    num = max(num, edge[0]);
    num = max(num, edge[1]);
  }
  vector<int> fathers(num + 1, 0);
  for (int i = 1; i < fathers.size(); ++i) {
    fathers[i] = i;
  }
  for (auto edge : edges) {
    if (!merge(fathers, edge)) {
      return edge;
    }
  }
  return {};
}

int main() {
  vector<vector<int>> edges = {{1, 2}, {1, 3}, {2, 4}, {3, 4}, {2, 5}};
  auto redundant_edge = findRedundantEdge(edges);
  printVec("o118", redundant_edge);

  return 0;
}
